package _11_整理题目._6_模拟设计._设计新的数据结构;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


/**
 *
 *
 * LRU：(Least Recently Used) 最近最久未使用
 * 不论 get 还是 put 都要记得更新 key 到最新位置
 * 
 * 使用 LinkedHashMap 数据结构存储数据，可以保存顺序的 key-value
 * 记录允许的最大容量 capacity
 * 实现 get set 时 注意 都要更新 key-value
 *
 * LinkedHashMap 注意
 *      LinkedHashMap是否允许空	    Key和Value都允许空
 *      LinkedHashMap是否允许重复数据	Key重复会覆盖、Value允许重复
 *      LinkedHashMap是否有序	    有序
 *      LinkedHashMap是否线程安全	    非线程安全
 * 
 * 构造函数
 *      初始化一个 LinkedHashMap 存储 key value ，LinkedHashMap put 是有序的
 *      初始化容量 capacity 注意 this 赋值不能省略
 * 
 * get(key)
 *      key 是否存在
 *          删除 key
 *          添加 key value
 *      否则
 *          return -1
 *      
 * put(key, value)
 *      key 是否存在
 *          删除 key
 *          添加 key value
 *      否则
 *          容量是否够
 *              添加 key value
 *          否则
 *              删除第一个key
 *              添加新的 key value
 *      
 */
class _01_实现LRUCache {

    private Map<Integer, Integer> map;
    private int capacity;
    
    public _01_实现LRUCache(int capacity) {
        this.map = new LinkedHashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key)) {
            int value = map.get(key);
            map.remove(key);
            map.put(key, value);
            return value;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
        } else {
            if(map.size() < capacity) {
                map.put(key, value);
            } else {
                Iterator it = map.keySet().iterator();
                map.remove(it.next());
                map.put(key, value);
            }
        }
    }
    
    
    public static void main(String[] args) {
        _01_实现LRUCache lRUCache = new _01_实现LRUCache(3);
        lRUCache.put(2, 2);
        lRUCache.put(1, 1);
        System.out.println(lRUCache.get(2));
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(2));
        lRUCache.put(3, 3);
        lRUCache.put(4, 4);
        System.out.println(lRUCache.get(3));
    }
    
}